/**
 * 找出字符串中第一个匹配项的下标
 *
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
 *
 * 示例 1：
 * 输入：haystack = "sadbutsad", needle = "sad"
 * 输出：0
 * 解释："sad" 在下标 0 和 6 处匹配。
 * 第一个匹配项的下标是 0 ，所以返回 0 。
 *
 * 示例 2：
 * 输入：haystack = "leetcode", needle = "leeto"
 * 输出：-1
 * 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 1. 使用 Set 集合 判断, 现将 s2 加入 集合中, 在遍历 s1, 如果有重复的, 就返回结果
 * 时间复杂度 : O(n)
 * 空见复杂度 : O(1)
 *
 * 2. 用 String 自带的方法判断
 */

public class Main {

    // 1. Set集合
    public int strStr1(String s1, String s2) {

        // 定义 Set集合
        Set<String> hash = new HashSet<>();

        // 将要找的 String 加入 集合
        hash.add(s2);

        int n1 = s1.length();
        int n2 = s2.length();

        // 遍历, 要注意越界, 因为 substring函数, 后面是开区间, 所以, 在取范围要注意是多取一个
        for (int i = 0; i <= n1 - n2; i++) {

            // 切割出等长的 String
            String s = s1.substring(i, i + n2);

            // 判断是重复
            if (hash.contains(s)) {
                return i;
            }
        }

        // 没有重发返回 -1
        return -1;
    }

    // 2. 使用 String自带的方法
    public int strStr(String s1, String s2) {
        if (!s1.contains(s2)) {
            return -1;
        }
        return s1.indexOf(s2);
    }
}